'''
给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

解题思路：递归解法中序取对应值 重点是返回节点不是节点值
'''
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        self.stack = []
        self.midOrder(pRoot)
        return self.stack[k - 1] if 0 < k <= len(self.stack) else None

    def midOrder(self, pRoot):
        if not pRoot: return
        self.midOrder(pRoot.left)
        self.stack.append(pRoot)
        self.midOrder(pRoot.right)

a8 = TreeNode(11)
a2 = TreeNode(5)
a3 = TreeNode(6)
a4 = TreeNode(7)
a5 = TreeNode(8)
a6 = TreeNode(9)
a7 = TreeNode(10)

a3.left = a2
a3.right = a4
a7.left = a6
a7.right = a8
a5.left = a3
a5.right = a7

s = Solution()
print(s.KthNode(a5, 1))